package com.YOUtils.DataStucture;

import com.YOUtils.YException.YNullPointerException;
import com.yum.Iterator.List.YArrayList.YLinkedList.YLinkedList;

import java.util.*;

/**
 * Created on 2023/6/20
 * 无向图(Graph) 邻连表 实现
 * @Time 20:41
 * @Program YOUilt
 * @Author YoHaNe/XiaoShuai
 */
public class Graph<T> {

    private final int nodeCount;

    private Set<GraphNode<T>>[] adj;

    public Graph(int nodeCount) {
        this.nodeCount = nodeCount;
        adj = new LinkedHashSet[nodeCount];
        for(int i=0;i<nodeCount;i++){
            adj[i] = new LinkedHashSet<>();
            adj[i].add(new GraphNode<T>(null,i));
        }
    }

    public void link(int v,int w){
        adj[v].add(findNode(w));
        adj[w].add(findNode(v));
    }

    public GraphNode<T> findNode(int num){
        if(num > nodeCount || num < 0)
            throw new YNullPointerException();
        for(GraphNode<T> nod : adj[num])
            return nod;
        return null;
    }

    public void DFS(int v,boolean[] visited){
        visited[v] = true;
        System.out.println(v + "  ");
        for(GraphNode<T> node : adj[v]){
            if(!node.visited)
                DFS(node.num,visited);
        }
    }

    private static class GraphNode<T>{
        T data;
        int num;
        boolean visited;
        public GraphNode(T data,int num) {
            this.data = data;
            this.num = num;
            visited = false;
        }

        public boolean insertData(T data){
            return (this.data = data) != null;
        }

        public boolean isVisited() {
            return visited;
        }

        public void setVisited(boolean visited) {
            this.visited = visited;
        }
    }



}
